The present invention is related to network data switches and more particularly to a syntax-based packet classification method and apparatus therefor.
Modern high performance switches, routers, traffic management devices and other network equipment generally process and transmit digital data that have been formatted into data packets, with each packet having one or more packet headers and packet data.
Referring to FIGS. 10A and 10B, a typical networking systems achieve communication between entities using a layered protocol architecture. A data packet is encoded according to the protocol layer. At each layer, a packet header containing protocol control information is concatenated with the data from the higher layer. This combination of data from the higher layer and control information is known as a protocol data unit (PDU). In general, the data packet is a multi-layer data structure that starts with a protocol header for the first layer 1002, followed by the higher layer headers 1004, 1006, 1008, and ends with data from the protocol data of the top layer 1008. FIG. 10B illustrates a flattened view of a typical arrangement of such hierarchically encapsulated packets.
A network protocol family usually has dependencies among the protocols. One protocol may require a specific lower layer protocol support, while the others may be built upon several different lower layers. For example, FIG. 6 shows a subset of a TCP/IP protocol suite structure. The dependencies in the protocol suite are reflected by the packet data formats accordingly.
Packet protocol classification plays a key role in the decision making process of modern high performance networking equipment. An incoming packet is analyzed and compared with a set of policy rules that identify certain packet attributes that require special processing. The result provides information about the protocol encapsulation format and matched policies of the received packet. Processing decisions are made based on the identified encapsulation format and policy information contained in the packet. In the process of making decisions about how to process the packet one must examine the packet layer by layer. Thus, in order to do the analysis of layer N, one needs to have made a similar analysis of layer N−1. Likewise, in order to do the analysis of layer N−1, one needs to have made a similar analysis of layer N−2, and so on.
Packet classification is an operation that is common to all packet routing and switching devices. For example, firewall filtering requires packets to be classified so that certain identified packets can be eliminated from the outgoing traffic. Packet classification is necessary to implement policy-based routing. Router access lists require packets to be classified for subsequent routing processing. Packet classification is used to identify different packets for collecting user statistics for performance monitoring and billing purposes.
A standard prior art method of processing packets uses protocol discrimination software to analyze packet protocol structure and to classify a packet according to a set of policies. The protocol discrimination software code usually compares, layer by layer, the key control or data fields of the packet. A decision tree is crafted to direct the processor to the discrimination code for the next layer when processing of the discrimination code at the previous layer is finished.
The software solutions require a CPU to run at a clock rate that is about an order of magnitude higher than the data receive clock rate in order to adequately process and route incoming packets in real time. The rapid growth in available network bandwidth makes a pure software approach expensive, impractical, and increasingly difficult to realize.
Hardware-based fixed protocol identifiers and programmable field detectors are capable of operating at much higher clock rates. These techniques inspect data fields in fixed or programmable offset positions in a packet. The fixed protocol identifiers usually recognize encapsulation protocols that are widely used, such as IP (internet protocol), VLAN (IEEE 802.1Q), and SNAP (subnet access protocol) encoded LLC (logical link control). The programmable field detectors allow limited flexibility to support customized classification rules. Since hardware identifiers and detectors can do several data field extractions and comparisons in parallel, these techniques are used to improve the processing speed of the discrimination software.
However, conventional hardware protocol identifiers, even systems enhanced with software control, can only handle a small number of simple classification rules. To provide quality of service (QoS) and fine grain traffic management, future networking applications require packet classifiers capable of handling large numbers of customized policies. These customized policies usually need to match several fixed or variable length data fields in several layers of packet headers with complex dependencies. Moreover, the end user who does not have access to the software code running in the equipment must have some means to modify these policies according to specific application requirements, without having to overhaul the software running the equipment.
In a co-pending application (U.S. application Ser. No. 09/538,132 filed Mar. 29, 2000 which is herein fully incorporated by reference and entitled “Method and Apparatus for Programmable Lexical Packet Classifier,” a novel hardware lexical packet classifier is disclosed for providing line rate packet classification capability. The technique is based on regular expressions which are mapped to a DFA (deterministic finite automaton). The invention provides an effective solution for low layer packet classification applications.
However, the foregoing inventive lexical packet classification technique is not appropriate as packetization policies move up in the protocol stack. To illustrate why this is so, refer to FIG. 6 which shows a subset of the structural hierarchy of the TCP/IP protocol suite. At the lowest level are Ethernet packets, VLAN Ethernet packets, SNAP-encoded LLC, and so on. Lexical scanning is appropriate for identifying these low-level packets. The lexical packet classifier scans the packet data without structural knowledge; i.e., the constituent data bytes of a packet are scanned with the same DFA without knowing which layer of protocol structure the data bytes are coming from. To get to a high layer data field, the regular expression rule must contain the complete description of the protocol structure from the first (outermost, lowest) layer to the last (innermost, highest) layer. This is not a problem for policies that only deal with one or two protocol layers. However, to define a higher layer policy, the regular expressions become complicated because they need to describe all of the valid encapsulation options at the lower layers of a packet just to provide the hardware scanner with the knowledge to skip the valid lower layer headers before it gets to the top. Rules like this are mapped into DFAs with large numbers of states that are very expensive to implement in hardware. Furthermore, as the regular expressions get complicated, the policy set definitions become hard for an end user to understand, define, and maintain. Therefore, the hardware lexical analysis technique is only practical for lower layer applications.
What is needed is a technique capable of recognizing packets at line rates. There is a need for a technique which can recognize the internal structure of packets in real time as they arrive to the switching or routing device. It is desirable to provide the capability of classifying incoming packets on the basis of the multitude of packet layers comprising each incoming packet.